package com.zj.leetcode.easy.greed;

import java.util.HashMap;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 下一个更大元素 I
 * 496 next-greater-element-i
 * @author: Zhang Bo
 * @create: 2022-04-14 10:55:28
 **/
public class NextGreaterElementI {
    public static void main(String[] args) {
        Solution solution = new NextGreaterElementI().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 这道题的关键是：
         * 如果能够找到 并将 nums2 的每个元素的 右侧 的 第一个 比 x 大的元素存起来。
         * 那一切变得迎刃而解了。
         * <p>
         * nums1 = [4,1,2],
         * nums2 = [1,3,4,2].
         *
         * 关于单调栈的使用自己举两个例子就明白了。
         * @param nums1
         * @param nums2
         * @return
         */
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {

            Stack<Integer> stack = new Stack<>();
            HashMap<Integer, Integer> map = new HashMap<>();

            int[] ret = new int[nums1.length];
            for (int num : nums2) {
                while (!stack.isEmpty() && stack.peek() < num) {
                    map.put(stack.pop(), num);
                }
                stack.push(num);
            }

            for (int i = 0; i < nums1.length; i++) {
                ret[i] = map.getOrDefault(nums1[i], -1);
            }

            return ret;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}